/*
 * HashExtensible.cpp
 *
 *  Created on: 15/04/2013
 *      Author: pancho
 */

#include "HashExtensible.h"
#include "Bloque.h"

HashExtensible::HashExtensible(string path, string tipo, unsigned int tamanioBloque) {
	this->ListaDeNumerosDeBloque = new list<unsigned short int>();
	this->archivo = new ArchivoBloques(path, tipo, tamanioBloque);
	this->tamanioBloque = tamanioBloque;
	this->contadorDeIds = 0;

	//HABRIA Q MODIFICAR ESTO PARA AGREGAR UN PATH
	//PARA PODER BORRARLO DESDE AFUERA
	int pos = path.rfind('.');
	string path2 = path.substr(0, pos);
	path2 += "tabla";
	this->tabla = new ArchivoRV(path2);
	char* sTabla = new char[250*sizeof(unsigned short int) + sizeof(unsigned int)];
	if(this->tabla->Leer(0, (char*)&this->contadorDeIds) == -1) {
		ListaDeNumerosDeBloque->push_back(0);

		Bloque * nuevoBloque = new Bloque();
		nuevoBloque->setNumeroBloque(0);
		nuevoBloque->setTamanioDispersion(1);
		nuevoBloque->setTamanioBloque(tamanioBloque);
		this->archivo->AgregarBloque(nuevoBloque->blockToChar(),tamanioBloque);
		delete nuevoBloque;

		delete sTabla;
	}
	else {
		this->cargarTabla();
	}
}

void HashExtensible::cargarTabla() {
	this->tabla->Leer(0, (char*)&(this->contadorDeIds));
	char* sTabla = new char[250*sizeof(unsigned short int) + sizeof(unsigned int)];
	unsigned int tamanio = this->tabla->Leer(8, sTabla);
	unsigned int posicion = 0;

	while ( posicion < tamanio) {
		unsigned short int numeroBloque;
		memcpy(&numeroBloque, &(sTabla[posicion]), sizeof(unsigned short int));
		posicion += sizeof(unsigned short int);
		this->ListaDeNumerosDeBloque->push_back(numeroBloque);
	}
	delete sTabla;
}

void HashExtensible::persistirTabla() {
	int tamanioDatosTabla = this->ListaDeNumerosDeBloque->size() * sizeof(unsigned short int);
	char* datosTabla = new char[tamanioDatosTabla];
	int posicion = 0;
	list<unsigned short int>::iterator iteradorLista = this->ListaDeNumerosDeBloque->begin();
	while (iteradorLista != this->ListaDeNumerosDeBloque->end()) {
		unsigned short int numeroBloque = *iteradorLista;
		memcpy(&(datosTabla[posicion]), (char*)&numeroBloque, sizeof(unsigned short int));
		posicion += sizeof(unsigned short int);
		iteradorLista++;
	}

	char aux[4];
	if(this->tabla->Leer(0, aux) != -1) {
		this->tabla->Borrar(8);
		this->tabla->Borrar(0);
	}
	this->tabla->Escribir(sizeof(unsigned int), (char*)&(this->contadorDeIds));
	this->tabla->Escribir(tamanioDatosTabla, datosTabla);
	delete datosTabla;
}



void HashExtensible::duplicarse() {
	int tamanioDeLista = ListaDeNumerosDeBloque->size();
	list<unsigned short int>::iterator iteradorLista = ListaDeNumerosDeBloque->begin();

	for(int i=0; i < tamanioDeLista; i++)
	{
		ListaDeNumerosDeBloque->push_back(*iteradorLista);
		iteradorLista++;
	}

}

//Devuelve falso si no se pueden dispersar las claves por overflow del bloque
bool HashExtensible::redispersarClaves(Bloque* bloqueLLeno, Bloque* bloqueNuevo, Registro* unRegistroNuevo) {

	bool insercionValida = true;
	list<Registro*> * nuevalistaBloqueLleno = new list<Registro*>;
	list<Registro*> * viejaListaBloqueLleno = new list<Registro*>;

	//Creo una lista con todas las claves a redispersar
	viejaListaBloqueLleno->assign(bloqueLLeno->getListaRegistros()->begin(),bloqueLLeno->getListaRegistros()->end());
	viejaListaBloqueLleno->push_back(unRegistroNuevo);

	//Le ingreso una lista vacia al bloque lleno
	bloqueLLeno->setListaRegistros(nuevalistaBloqueLleno);

	list<Registro*>::iterator iteradorListaVieja = viejaListaBloqueLleno->begin();
	while(insercionValida && iteradorListaVieja != viejaListaBloqueLleno->end())
	{
		Registro * unRegistro = *iteradorListaVieja;
		if(getPos(unRegistro->devolverDato(this)) == bloqueLLeno->getNumeroBloque() )
		{
			insercionValida=bloqueLLeno->InsertarRegistro(unRegistro);
		}
		else
		{
			insercionValida=bloqueNuevo->InsertarRegistro(unRegistro);
		}
		iteradorListaVieja++;
	}

	if (insercionValida)
	{
		delete viejaListaBloqueLleno;
	}
	else
	{
		viejaListaBloqueLleno->pop_back();
		bloqueLLeno->setListaRegistros(viejaListaBloqueLleno);
		list<Registro*> * nuevalistaBloqueNuevo = new list<Registro*>;
		bloqueNuevo->setListaRegistros(nuevalistaBloqueNuevo);
	}

	return insercionValida;

}

void HashExtensible::dividirse() {
	int tamanioDeLista = ListaDeNumerosDeBloque->size();

	//Elimino de atras hacia adelante, la mitad de elementos de la tabla
	for(int i=tamanioDeLista/2; i < tamanioDeLista; i++)
	{
		ListaDeNumerosDeBloque->pop_back();
	}
}

bool HashExtensible::puedeDividirseEnDos() {
	bool sePuedeDividirEnDos=true;

	list<unsigned short int>::iterator iteradorListaPrimeraMitad = ListaDeNumerosDeBloque->begin();
	list<unsigned short int>::iterator iteradorListaSegundaMitad = ListaDeNumerosDeBloque->begin();

	int tamanioDeLista = ListaDeNumerosDeBloque->size();
	int mitadDeLista=tamanioDeLista/2;
	int i= mitadDeLista;

	//Muevo el iterador al comienzo de la segunda mitad de la tabla
	for(int j=0; j <mitadDeLista; j++)
		iteradorListaSegundaMitad++;

	while( (i < tamanioDeLista) && (sePuedeDividirEnDos))
	{
		if((*iteradorListaPrimeraMitad) != (*iteradorListaSegundaMitad))
		{
			sePuedeDividirEnDos = false;
		}
		iteradorListaPrimeraMitad++;
		iteradorListaSegundaMitad++;
		i++;
	}

	return sePuedeDividirEnDos;
}

void HashExtensible::modificarHashConNuevoBloque(unsigned short int numeroDelNuevoBloque, int posAModificar,unsigned short int nuevoTamanioDispersion) {

	unsigned int nroDeOcurrenciasDelBloque = this->getListaDeNroDeBloques()->size() / nuevoTamanioDispersion;
	setPos(posAModificar,numeroDelNuevoBloque);
	for(unsigned int i=0; i < nroDeOcurrenciasDelBloque; i++)
	{
		posAModificar= posAModificar + nuevoTamanioDispersion;
		this->ajustarALista(posAModificar);
		setPos(posAModificar, numeroDelNuevoBloque);
	}

}

void HashExtensible::ajustarALista(int & posAModificar)
{
	if(posAModificar < 0)
	{
		posAModificar = this->getListaDeNroDeBloques()->size()+posAModificar;
	}else if((unsigned int)posAModificar >= this->getListaDeNroDeBloques()->size())
	{
		posAModificar = posAModificar-this->getListaDeNroDeBloques()->size();
	}
}

//Pre: La posición debe ser una posición válida
unsigned short int HashExtensible::getPos(int posEnTabla)
{
	this->ajustarALista(posEnTabla);
	list<unsigned short int>::iterator iteradorLista = ListaDeNumerosDeBloque->begin();

	for(int i=0; i < posEnTabla; i++)
	{
		iteradorLista++;
	}

	return (*iteradorLista);
}

//Pre: la pos en tabla debe ser valida.
void HashExtensible::setPos(int posEnTabla,unsigned short int nuevoValor)
{
	this->ajustarALista(posEnTabla);
	list<unsigned short int>::iterator iteradorLista = ListaDeNumerosDeBloque->begin();

	for(int i=0; i < posEnTabla; i++)
	{
		iteradorLista++;
	}
	(*iteradorLista)=nuevoValor;

}


/*La funcion de dispersion para un tipo de dato string realiza lo siguiente:
 * Si la cantidad de caracteres es menor o igual a cuatro, concatena los valores ascii de toda la cadena
 * y se aplica la division entera con el tamanio de tabla
 * Si es mayor a 4, concatena los dos primeros caracteres con los dos ultimos caracters
 * y se aplica la division entera con el tamanio de tabla
 */
int HashExtensible::fd(string unString)
{

	int posDeDispersion=0;
	unsigned int pos=0;
	if(unString.size()<= 4)
	{
		while((pos < unString.size()))
		{
			posDeDispersion = int(toupper(unString[pos])) * pow(10,pos) + posDeDispersion;
			pos++;
		}
	}
	else
	{
			posDeDispersion = int(toupper(unString[0])) * pow(10,0) + posDeDispersion;
			posDeDispersion = int(toupper(unString[1])) * pow(10,2) + posDeDispersion;
			posDeDispersion = int(toupper(unString[unString.size()-2])) * pow(10,4) + posDeDispersion;
			posDeDispersion = int(toupper(unString[unString.size()-1])) * pow(10,6) + posDeDispersion;
	}

	posDeDispersion = posDeDispersion % (ListaDeNumerosDeBloque->size());
	return posDeDispersion;
}

int HashExtensible::fd(unsigned int unNumero)
{
	int posDeDispersion=unNumero % (ListaDeNumerosDeBloque->size());
	return posDeDispersion;
}



//Se debe haber chequeado que la clave esta en el bloque
//Devuelve una lista con un elemento, el offset asociado al id
list<unsigned int> *HashExtensible::BuscarClave(unsigned int id) {
	int nroBloque = this->getPos(fd(id));
	char* bloqueCaracter =this->archivo->RecuperarBloque(nroBloque);
	Bloque *unBloque = new Bloque("unsigned int",bloqueCaracter);
	if(!unBloque->EstaRegistro(id))
	{
		delete unBloque;
		return NULL;
	}
	else
	{
		list<unsigned int> * listaIds = new list<unsigned int>;
		RegistroOffset *unRegistroOffset = dynamic_cast<RegistroOffset*> (unBloque->BuscarRegistro(id));
		listaIds->push_back(unRegistroOffset->getOffset());
		delete unBloque;
		return listaIds;
	}
}

//Se debe haber chequeado que la clave esta en el bloque
//Devuelve una copia de la lista de IDs del registro que contiene la clave id
list<unsigned int>* HashExtensible::BuscarClave(string titulo) {
	int nroBloque = this->getPos(fd(titulo));
		char* bloqueCaracter =this->archivo->RecuperarBloque(nroBloque);
		Bloque *unBloque = new Bloque("char*",bloqueCaracter);
		if(!unBloque->EstaRegistro(titulo))
		{
			delete unBloque;
			return NULL;
		}
		else
		{
			list<unsigned int> * listaIds = new list<unsigned int>;
			listaIds->assign(unBloque->BuscarRegistro(titulo)->getId()->begin(),unBloque->BuscarRegistro(titulo)->getId()->end());
			delete unBloque;
			return listaIds;
		}
}
unsigned int HashExtensible::Agregar(string cancion, unsigned int id)
{
	RegistroTitulo * unRegistroNuevo = new RegistroTitulo();
	unRegistroNuevo->setTitulo(cancion);
	unRegistroNuevo->agregarId(id);

	//Pedir al registro el dato al cual se le debe realizar la funcion de dispersion
	 int posEnTabla = unRegistroNuevo->devolverDato(this);


	//Pedir el bloque al archivo (Si no existe, se crea) (Se guarda en una variable de tipo Bloque)
	 unsigned short int nroBloque = this->getPos(posEnTabla);
	Bloque *unBloque = new Bloque("char*", archivo->RecuperarBloque(nroBloque));

	//Dar de alta el nuevo registro en el bloque
	bool insercionValida = unBloque->InsertarRegistro(unRegistroNuevo);

	while (!insercionValida)
	{
	 		unsigned short int viejoTamanioDeDispersion = unBloque->getTamanioDispersion();
	 		unBloque->DuplicarTamanioDispersion();
	 		unsigned short int nuevoTamanioDispersion = unBloque->getTamanioDispersion();

	 		//Creo un nuevo bloque para la nueva dispersion
	 		Bloque* nuevoBloque = new Bloque();
	  		nuevoBloque->setTamanioDispersion(nuevoTamanioDispersion);
	 		nuevoBloque->setTamanioBloque(unBloque->getTamanioBloque());

	 		//Se crea (o se utiliza) un bloque en el archivo
	 		unsigned short int numeroDelNuevoBloque = archivo->AgregarBloque(nuevoBloque->blockToChar(), nuevoBloque->getTamanioBloque());

	  		if (viejoTamanioDeDispersion == this->ListaDeNumerosDeBloque->size())
	  			this->duplicarse();
	  		else //si TamanioDispersion < TamTabla entonces
	  			modificarHashConNuevoBloque(numeroDelNuevoBloque,posEnTabla, nuevoTamanioDispersion);

	  		//Reemplazo la pos en tabla del bloque desbordado por el nuevo bloque
	  		nuevoBloque->setNumeroBloque(numeroDelNuevoBloque);
	  		this->setPos(posEnTabla, numeroDelNuevoBloque);

	  		//Redisperso los registros del bloque desbordado y el nuevo registro
	 		insercionValida = redispersarClaves(unBloque, nuevoBloque, unRegistroNuevo);

	 		if(insercionValida)
	 		{
	 			char* bloqueEnChar = nuevoBloque->blockToChar();
	 			archivo->ModificarBloque(nuevoBloque->getNumeroBloque(),bloqueEnChar, nuevoBloque->getTamanioBloque() );
	 			delete []bloqueEnChar;
	 		}
	 		else
	 		{
	 			this->archivo->LiberarBloque(numeroDelNuevoBloque);
	 			delete nuevoBloque;
	 		}

	 }

	char* bloqueEnChar = unBloque->blockToChar();
	archivo->ModificarBloque(nroBloque,bloqueEnChar,unBloque->getTamanioBloque() );
	delete []bloqueEnChar;
	delete unBloque;

	return 0;
}


unsigned int HashExtensible::Agregar(unsigned int offset) {
	RegistroOffset * unRegistroNuevo = new RegistroOffset();
	unRegistroNuevo->setOffset(offset);
	unRegistroNuevo->agregarId(this->aumentarContadorIds());

	//Pedir al registro el dato al cual se le debe realizar la funcion de dispersion
	 int posEnTabla = unRegistroNuevo->devolverDato(this);


	//Pedir el bloque al archivo (Si no existe, se crea) (Se guarda en una variable de tipo Bloque)
	 unsigned short int nroBloque = this->getPos(posEnTabla);
	Bloque *unBloque = new Bloque("unsigned int", archivo->RecuperarBloque(nroBloque));


	//Dar de alta el nuevo registro en el bloque
	bool insercionValida = unBloque->InsertarRegistro(unRegistroNuevo);

	while (!insercionValida)
	{
	 		unsigned short int viejoTamanioDeDispersion = unBloque->getTamanioDispersion();
	 		unBloque->DuplicarTamanioDispersion();
	 		unsigned short int nuevoTamanioDispersion = unBloque->getTamanioDispersion();

	 		//Creo un nuevo bloque para la nueva dispersion
	 		Bloque* nuevoBloque = new Bloque();
	  		nuevoBloque->setTamanioDispersion(nuevoTamanioDispersion);
	 		nuevoBloque->setTamanioBloque(unBloque->getTamanioBloque());

	 		//Se crea (o se utiliza) un bloque en el archivo
	 		unsigned short int numeroDelNuevoBloque = archivo->AgregarBloque(nuevoBloque->blockToChar(), nuevoBloque->getTamanioBloque());

	  		if (viejoTamanioDeDispersion == this->ListaDeNumerosDeBloque->size())
	  			this->duplicarse();
	  		else //si TamanioDispersion < TamTabla entonces
	  			modificarHashConNuevoBloque(numeroDelNuevoBloque,posEnTabla, nuevoTamanioDispersion);

	  		//Reemplazo la pos en tabla del bloque desbordado por el nuevo bloque
	  		nuevoBloque->setNumeroBloque(numeroDelNuevoBloque);
	  		this->setPos(posEnTabla, numeroDelNuevoBloque);

	  		//Redisperso los registros del bloque desbordado y el nuevo registro
	 		insercionValida = redispersarClaves(unBloque, nuevoBloque, unRegistroNuevo);

	 		if(insercionValida)
	 		{
	 			char* bloqueEnChar = nuevoBloque->blockToChar();
	 			archivo->ModificarBloque(nuevoBloque->getNumeroBloque(),bloqueEnChar, nuevoBloque->getTamanioBloque() );
	 			delete []bloqueEnChar;
	 		}
	 		else
	 		{
	 			this->archivo->LiberarBloque(numeroDelNuevoBloque);
	 			delete nuevoBloque;
	 		}

	 }

	char* bloqueEnChar = unBloque->blockToChar();
	archivo->ModificarBloque(nroBloque,bloqueEnChar,unBloque->getTamanioBloque() );
	delete []bloqueEnChar;
	delete unBloque;

	return this->getContadorIds();
}

//Pos:Devuelve 0 si se pudo dar de baja el elemento
//Pos2:Devuelve 1 si no se pudo dar de baja el elemento a causa de que no se encuentra en el hash
int HashExtensible::baja(unsigned int id) {
	//Pedir al registro el dato al cual se le debe realizar la funcion de dispersion
	 int posEnTabla = this->fd(id);

	 unsigned short int nroBloque = this->getPos(posEnTabla);
	 char* bloqueEnCaracter = this->archivo->RecuperarBloque(nroBloque);
	 Bloque *unBloque = new Bloque("unsigned int", bloqueEnCaracter);

	 if(unBloque->EstaRegistro(id))
	 {
		 unBloque->eliminarId(id);
		 int desplazamiento = (int) (unBloque->getTamanioDispersion() / 2);
		 int posAChequearPorDetras = posEnTabla-desplazamiento;
		 int posAChequearPorDelante = posEnTabla+desplazamiento;
		 ajustarALista(posAChequearPorDelante);
		 ajustarALista(posAChequearPorDetras);
		 bool puedeLiberarse = (getPos(posAChequearPorDelante) == getPos(posAChequearPorDetras));
		 puedeLiberarse = puedeLiberarse && (posAChequearPorDelante != posEnTabla);

		 if(unBloque->getListaRegistros()->size() == 0 && puedeLiberarse)
		 {
			 unsigned short int nroBloqueAReferenciar = getPos(posEnTabla-desplazamiento);
			 bloqueEnCaracter = this->archivo->RecuperarBloque(nroBloqueAReferenciar);
			 Bloque *bloqueAReferenciar = new Bloque("unsigned int", bloqueEnCaracter);

			 bloqueAReferenciar->DividirTamanioDispersion();
			 unsigned short int nuevoTamanioDispersion = bloqueAReferenciar->getTamanioDispersion();
			 this->modificarHashConNuevoBloque(nroBloqueAReferenciar,posEnTabla,nuevoTamanioDispersion);

			 bloqueEnCaracter = bloqueAReferenciar->blockToChar();
			 this->archivo->ModificarBloque(nroBloqueAReferenciar, bloqueEnCaracter, bloqueAReferenciar->getTamanioBloque());
			 delete[]bloqueEnCaracter;

			 this->archivo->LiberarBloque(nroBloque);
			 delete bloqueAReferenciar;

			 if(this->puedeDividirseEnDos())
				 this->dividirse();

		 }
		 else
		 {
			 bloqueEnCaracter = unBloque->blockToChar();
			 this->archivo->ModificarBloque(nroBloque,bloqueEnCaracter, unBloque->getTamanioBloque());
			 delete[] bloqueEnCaracter;
		 }
	 }
	 else
	 {
		 cout << "El elemento que se quiere eliminar no esta en el bloque" <<endl;
		 return 1;
	 }

	 delete unBloque;

	return 0;
}

//Pos:Devuelve 0 si se pudo dar de baja el elemento
//Pos2:Devuelve 1 si no se pudo dar de baja el elemento a causa de que no se encuentra en el hash
int HashExtensible::baja(string titulo,unsigned int id) {
	//Pedir al registro el dato al cual se le debe realizar la funcion de dispersion
	 int posEnTabla = this->fd(titulo);
	 unsigned short int nroBloque = this->getPos(posEnTabla);
	 char* bloqueEnCaracter = this->archivo->RecuperarBloque(nroBloque);
	 Bloque *unBloque = new Bloque("char*", bloqueEnCaracter);

	 if(unBloque->EstaRegistro(titulo))
	 {
		 unBloque->eliminarId(titulo,id);
		 int desplazamiento = (int) (unBloque->getTamanioDispersion() / 2);
		 int posAChequearPorDetras = posEnTabla-desplazamiento;
		 int posAChequearPorDelante = posEnTabla+desplazamiento;
		 ajustarALista(posAChequearPorDelante);
		 ajustarALista(posAChequearPorDetras);
		 bool puedeLiberarse = (getPos(posAChequearPorDelante) == getPos(posAChequearPorDetras));
		 puedeLiberarse = puedeLiberarse && (posAChequearPorDelante != posEnTabla);

		 if(unBloque->getListaRegistros()->size() == 0 && puedeLiberarse)
		 {
			 unsigned short int nroBloqueAReferenciar = getPos(posEnTabla-desplazamiento);
			 bloqueEnCaracter = this->archivo->RecuperarBloque(nroBloqueAReferenciar);
			 Bloque *bloqueAReferenciar = new Bloque("char*", bloqueEnCaracter);

			 bloqueAReferenciar->DividirTamanioDispersion();
			 unsigned short int nuevoTamanioDispersion = bloqueAReferenciar->getTamanioDispersion();
			 this->modificarHashConNuevoBloque(nroBloqueAReferenciar,posEnTabla,nuevoTamanioDispersion);

			 bloqueEnCaracter = bloqueAReferenciar->blockToChar();
			 this->archivo->ModificarBloque(nroBloqueAReferenciar, bloqueEnCaracter, bloqueAReferenciar->getTamanioBloque());
			 delete[]bloqueEnCaracter;

			 this->archivo->LiberarBloque(nroBloque);
			 delete bloqueAReferenciar;

			 if(this->puedeDividirseEnDos())
				 this->dividirse();

		 }
		 else
		 {
			 bloqueEnCaracter = unBloque->blockToChar();
			 this->archivo->ModificarBloque(nroBloque,bloqueEnCaracter, unBloque->getTamanioBloque());
			 delete[] bloqueEnCaracter;
		 }
	 }
	 else
	 {
		 cout << "El elemento que se quiere eliminar no esta en el bloque" <<endl;
		 return -1;
	 }

	 delete unBloque;

	return 0;
}

HashExtensible::~HashExtensible() {
this->persistirTabla();
delete this->ListaDeNumerosDeBloque;
delete this->archivo;
delete this->tabla;
}

list<unsigned short int>* HashExtensible::getListaDeNroDeBloques()
{
	return this->ListaDeNumerosDeBloque;
}

unsigned int HashExtensible::getTamanioBloque() {
	return this->tamanioBloque;
}

void HashExtensible::setTamanioBloque(unsigned int nuevoTamanioBloque) {
	this->tamanioBloque = nuevoTamanioBloque;
}

unsigned int HashExtensible::aumentarContadorIds() {
	this->contadorDeIds++;
	return this->contadorDeIds;
}

unsigned int HashExtensible::getContadorIds() {
	return this->contadorDeIds;
}
